package BinaryTree;

class BinaryTree<T> {
	public BinaryTreeNode<T> root;
	private final int maxNodes=100;
	public BinaryTree()
	{
		 this.root = new BinaryTreeNode<T>();
	}    
	public BinaryTree(T x)
	{
		this.root = new BinaryTreeNode<T>(x);
	}

	/*
	*  为指定的父节点插入一个左子节点，
	* 若父节点为空则返回false；否则创建新节点p，
	* 若父节点无左子节点，则直接插入；
	* 若有，则将原左子节点作为p的左子节点，并将p设为新的左子节点。
	* */
	public boolean insertLeft(T x, BinaryTreeNode<T> parent)
	{ 
		if(parent==null)	return false;
		BinaryTreeNode<T> p= new BinaryTreeNode<T>(x);
		if(parent.lChild==null) parent.lChild = p;
		else
		{
			p.lChild = parent.lChild;
			parent.lChild = p;
		}
		return true;
	} 

    public boolean insertRight(T x, BinaryTreeNode<T> parent)
    { 
		if(parent==null)	return false;
		BinaryTreeNode<T> p= new BinaryTreeNode<T>(x);
		if(parent.rChild==null) parent.rChild = p;
		else
		{
			p.rChild = parent.rChild;
			parent.rChild = p;
		}
		return true; 
	}
    

    public boolean deleteLeft(BinaryTreeNode<T> parent)
    {
    	if(parent==null)	return false;
    	else
    	{
    		parent.lChild=null;
    		return true;
    	}
    } 

    public boolean deleteRight(BinaryTreeNode<T> parent)
    { 
    	if(parent==null)  	return false;
    	else
    	{
       		parent.rChild=null;
    		return true; 		
    	}
    } 
    /**
     * 具体实现部分
     * @param node
     */
  //输出二叉树的所有叶子节点
  	public void yezi(BinaryTreeNode<T> node)
  	{
  		if(node==null) return;
  		else
  		{
  			if (node.lChild==null&&node.rChild==null) {
  	  			System.out.print("叶子:"+node.getData());
			  }
  			else{
  				yezi(node.lChild);
  				yezi(node.rChild);
			  }
  		}  		
  	}
  //统计二叉树所有节点的总数
  	public int count(BinaryTreeNode<T> node)
  	{
  		int lc, rc, sum;
		if(node != null)
		{
			lc = count(node.lChild);
			rc = count(node.rChild);
			sum = lc+rc;
			return (sum+1);
		}
		else  return 0;

  	}
  	
    //在当前二叉树中查找数据x
    public BinaryTreeNode<T> search(BinaryTreeNode<T> node, T x){
    	if(node==null)
    		return null;
    	else{
    		if((node.getData()).equals(x)){
    			return node;
    		}			
    		else{
    			BinaryTreeNode<T> s=search(node.lChild,x);
    			if(s!=null)//避免不必要的右子树查找
    				return s;
    			else
    				return search(node.rChild,x);
    		}
    	}
    }

    //查找node的parent
    public BinaryTreeNode<T> search2(BinaryTreeNode<T> node, T x){
    	if(node==null)
    		return null;
    	else{
    		if(node.lChild!=null &&(node.lChild.getData()).equals(x)){	
    			return node;
    		}
    		if(node.rChild!=null &&(node.rChild.getData()).equals(x)){	
    			return node;
    		}
    		BinaryTreeNode<T> s=search2(node.lChild,x);
    		if(s!=null)
				return s;
			else
				return search2(node.rChild,x);
    	}
    }    
    
    //插入操作
    public boolean insertl(BinaryTreeNode<T> a, BinaryTreeNode<T> parent)
	{ 
		if(parent==null)	return false;
		//Node<T> p= new Node<T>(x);
		if(parent.lChild==null) parent.lChild = a;
		else
		{
			insertl(a,parent.lChild);
		}
		return true;
	} 
    //插入操作
    public boolean insertr(BinaryTreeNode<T> a, BinaryTreeNode<T> parent)
	{ 
		if(parent==null)	return false;
		//Node<T> p= new Node<T>(x);
		if(parent.rChild==null) parent.rChild = a;
		else
		{
			insertr(a,parent.rChild);
		}
		return true;
	} 
   //缩进打印
  	public void suojing(BinaryTreeNode<T> node, int i) {
  		if(node==null)return;
		for (int j = 0; j < i; j++) {
			System.out.print("-");
		}
		System.out.println(node.getData());
		suojing(node.lChild,++i);
		--i;
		suojing(node.rChild,++i);
		--i;
	}
	/*中序遍历*/
	public void inorder(BinaryTreeNode<T> node)
	{
		if(node==null) return;
		inorder(node.lChild);
		System.out.print(node.getData());
		inorder(node.rChild);
	}
	/*先序遍历*/
	public void preorder(BinaryTreeNode<T> node)
	{
		if(node==null) return;
		System.out.print(node.getData());
		preorder(node.lChild);
		preorder(node.rChild);
	}
	/*后序遍历*/
	public void postorder(BinaryTreeNode<T> node)
	{
		if(node==null) return;
		postorder(node.lChild);
		postorder(node.rChild);
		System.out.print(node.getData());
	}

	/*层次遍历*/
	public void levelorder()
	{
		BinaryTreeNode<T>[] queue= new BinaryTreeNode[this.maxNodes];
		int front,rear;
		if (this.root==null) return;
		front=-1;
		rear=0;
		queue[rear]=this.root;
		while(front!=rear)
		{
			front++;
			System.out.print(queue[front].getData());    /*???????????????*/
			/*???????????????????*/
			if (queue[front].lChild!=null)
			{ 
				rear++;
				queue[rear]=queue[front].lChild;
			}
			/*????????????????????*/
			if (queue[front].rChild!=null)
			{
				rear++;
				queue[rear]=queue[front].rChild;
			}
		}
	}

	/**
	 * 以缩进方式打印二叉树结构
	 * @param node 当前节点
	 * @param level 当前节点的层次（缩进级别）
	 */
	public void printTree(BinaryTreeNode<T> node, int depth) {
		if (node == null) {
			return;
		}

		// 先递归右子树
		printTree(node.rChild, depth + 1);

		// 打印当前节点
		for (int i = 0; i < depth; i++) {
			System.out.print("     ");
		}
		System.out.println(node.getData());

		// 再递归左子树
		printTree(node.lChild, depth + 1);
	}

	// 遍历
	public void traversal(int i)
	{
		switch(i)
		{
			case 0: preorder(this.root);break;
			case 1: inorder(this.root);break;
			case 2: postorder(this.root);break;
			default: levelorder();	
		}
	}
}